﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Trinity.Core.Lib;

namespace SequenceAssembler
{
	class TinyRepeatResolver
	{
		class ResolvableMatrix {
			public int Dimension { get { return data.Length; } }
			int[][] data;

			public ResolvableMatrix(int d) {
				data = new int[d][];
				for (int i = 0; i < d; ++i) {
					data[i] = new int[d];
					Array.Clear(data[i], 0, d);
				}
			}

			public int Get(int x, int y) {
				return data[x][y];
			}

			public void Increment(int x, int y) {
				++data[x][y];
			}

			public void Transpose() {
				for (int i = 0; i < Dimension - 1; ++i) {
					for (int j = i+1; j < Dimension; ++j) {
						int t = data[i][j];
						data[i][j] = data[j][i];
						data[j][i] = t;
					}
				}
			}

			/// <summary>
			/// All in-arc and out-arc has multiple paths
			/// We even do not need to look at twin to make
			/// sure it is unresolvable.
			/// </summary>
			/// <returns></returns>
			public bool ConflictForAll() {
				int conflictNum = 0;
				for (int i = 0; i < Dimension; ++i) {
					int notZero = 0;
					for (int j = 0; j < Dimension; ++j) {
						if (data[i][j] == 0) { continue; }
						++notZero;
					}
					for (int j = 0; j < Dimension; ++j) {
						if (i == j || data[j][i] == 0) { continue; }
						++notZero;
					}
					if (notZero > 1) { ++conflictNum; }
				}
				if (conflictNum == Dimension) { return true; }
				return false;
			}

			/// <summary>
			/// If it is not conflict for all then this resolvable
			/// test will tell you if it some arc meets both 3. and 4,
			/// thus resolvable.
			/// Caution only correct if you have considered twin.
			/// </summary>
			/// <returns></returns>
			public bool Resolvable() {
				int emptyNum = Dimension + Dimension;
				foreach (var row in data)
				{
					foreach (var z in row)
					{
						if (z != 0) {
							--emptyNum;
							break;
						}
					}
				}
				for (int i = 0; i < Dimension; ++i)
				{
					for (int j = 0; j < Dimension; ++j){
						if (data[j][i] != 0) {
							--emptyNum;
							break;
						}
					}
				}
				if (emptyNum == 0) { return true; }
				return false;
			}

			/// <summary>
			/// Find the outEntry for the given inEntry.
			/// </summary>
			/// <param name="inEntry"></param>
			/// <returns>-1 if unresolvable or outEntry</returns>
			public int OutEntry(int inEntry)
			{
				int outEntry = -1;
				for (int i = 0; i < Dimension; ++i)
				{
					if (data[inEntry][i] != 0)
					{
						if (outEntry != -1) {
							return -1;
						}
						outEntry = i;
					}
				}
				if (outEntry == -1) { return outEntry; }
				for (int i = 0; i < Dimension; ++i)
				{
					if (i != inEntry && data[i][outEntry] != 0) {
						return -1;
					}
				}
				return outEntry;
			}

			public override string ToString() {
				StringBuilder sb = new StringBuilder();
				foreach (var row in data) {
					foreach (var ele in row) {
						sb.Append(ele);
						sb.Append('\t');
					}
					sb.AppendLine();
				}
				return sb.ToString();
			}
		}

		public BackGraph bg { get; private set; }

		public TinyRepeatResolver(BackGraph backGraph) {
			bg = backGraph;
		}

		public void Resolve() {
			long before = bg.CellCount;
			long after = 0;
			SimpleCellMerger merger = new SimpleCellMerger(bg);
			while (before != after)
			{
				Console.WriteLine("Pre resolve cell count: {0}", bg.CellCount);
				before = bg.CellCount;
				ResolveOnce();
				merger.Merge();
				after = bg.CellCount;
				Console.WriteLine("Post resolve cell count: {0}", bg.CellCount);
			}
		}

		/// <summary>
		/// Resolve tiny repeats:
		/// 1. the node must be shorter than a read
		/// 2. the #in-arcs must be equal to #out-arcs
		/// 3. each in-arc must share some reads with one or more out-arcs
		/// My comment is that this is quite reserved, but to avoid mis-assembly.
		/// 4. if an in-arc only share with reads with one out-arc and
		/// and that out-arc have no other in-arc share reads with it,
		/// then the path goes through it is resolvable.
		/// 5. twin also has to be resolvable.
		/// 6. we stop resolving if current node has only one out-arc,
		/// since it is resolved.
		/// </summary>
		private void ResolveOnce() {
			int longestResolvable = 0;
			foreach (var il in bg.InsertLengths)
			{
				longestResolvable = Math.Max(longestResolvable, il.Length);
			}
			longestResolvable -= 2;
			List<long> celllist = new List<long>(bg.CellList);
			foreach (long id in celllist)
			{
				var cell = bg.LoadCell<SequenceCell>(id);
				if (cell == null) { continue; }
				if (cell.Size > longestResolvable || cell.Arcs.Count == 1)
				{ continue; } //1.

				long twinId = bg.TwinId(cell.Id);
				var twinCell = bg.LoadCell<SequenceCell>(twinId);
				if (cell.Arcs.Count != twinCell.Arcs.Count) { continue; } //2.

				// cells after cell
				long[] postIds = new long[cell.Arcs.Count];
				for (int i = 0; i < cell.Arcs.Count; ++i)
				{
					postIds[i] = cell.Arcs[i].Destination;
				}
				SequenceCell[] postCells = bg.LoadCells<SequenceCell>(postIds);
				//cells before twinCell
				long[] preTwinIds = new long[cell.Arcs.Count];
				for (int i = 0; i < cell.Arcs.Count; ++i)
				{
					preTwinIds[i] = bg.TwinId(cell.Arcs[i].Destination);
				}
				SequenceCell[] preTwinCells = bg.LoadCells<SequenceCell>(preTwinIds);
				//cells after twinCell
				long[] postTwinIds = new long[twinCell.Arcs.Count];
				for (int i = 0; i < twinCell.Arcs.Count; ++i)
				{
					postTwinIds[i] = twinCell.Arcs[i].Destination;
				}
				SequenceCell[] postTwinCells = bg.LoadCells<SequenceCell>(postTwinIds);
				//cells before cell
				long[] preIds = new long[twinCell.Arcs.Count];
				for (int i = 0; i < twinCell.Arcs.Count; ++i)
				{
					preIds[i] = bg.TwinId(twinCell.Arcs[i].Destination);
				}
				SequenceCell[] preCells = bg.LoadCells<SequenceCell>(preIds);

				ResolvableMatrix mx = new ResolvableMatrix(preCells.Length);
				fillMatrix(mx, preCells, postCells, (int) cell.Size);
				if (mx.ConflictForAll()) { continue; } //no hope to resolve
				mx.Transpose();
				fillMatrix(mx, preTwinCells, postTwinCells, (int)cell.Size);
				if (mx.ConflictForAll() || !mx.Resolvable()) { continue; } //no hope to resolve

				for (int i = 0; i < mx.Dimension; ++i)
				{
					if (twinCell.Arcs.Count == 1) {
						break;
					}
					int j = mx.OutEntry(i);
					if (j == -1)
					{
						continue;
					}

					int inEntry = j;
					int outEntry = i;
					int twinInEntry = i;
					int twinOutEntry = j;
					long freeId = GenerateFreeId();
					long freeTwinId = bg.TwinId(freeId);
					SequenceCell cellCopy = cell.NoArcCopy();
					SequenceCell twinCellCopy = twinCell.NoArcCopy();
					if (postCells[outEntry].Id == twinId && postTwinCells[twinOutEntry].Id == id)
					{
						//twin node special situation: Node -> Twin -> Node -> Twin
						cellCopy.Id = freeId;
						twinCellCopy.Id = freeTwinId;
						int arci = findArc(cell.Arcs, twinId);
						int twinArci = findArc(twinCell.Arcs, id);
						cellCopy.ConnectTo(freeTwinId, cell.Arcs[arci].Multiplicity);
						twinCellCopy.ConnectTo(freeId, twinCell.Arcs[twinArci].Multiplicity);
						cell.Arcs.RemoveAt(arci);
						twinCell.Arcs.RemoveAt(twinArci);
						bg.SaveCell(cellCopy);
						bg.SaveCell(twinCellCopy);
					}
					else if (postCells[outEntry].Id == twinId)
					{
						//twin node special situation: Node -> Twin
						Detach(cell, preCells[inEntry], cellCopy, twinCell, twinCellCopy, postTwinCells[twinOutEntry]);
					} 
					else if (postTwinCells[twinOutEntry].Id == id) {
						//twin node special situation: Twin -> Node
						Detach(twinCell, preTwinCells[twinInEntry], twinCellCopy, cell, cellCopy, postCells[outEntry]);
					}
					else
					{
						Detach(cell, preCells[inEntry], cellCopy, postCells[outEntry]);
						Detach(twinCell, preTwinCells[twinInEntry], twinCellCopy, postTwinCells[twinOutEntry]);
						bg.SaveCell(cellCopy);
						bg.SaveCell(twinCellCopy);
					}
				}
				bg.SaveCell(cell);
				bg.SaveCell(twinCell);
				bg.SaveCells(preCells);
				bg.SaveCells(postCells);
				bg.SaveCells(preTwinCells);
				bg.SaveCells(postTwinCells);
			}
		}

		/// <summary>
		/// Relink the preCell to cellCopy, and cellCopy links to the postCell. Delink cell to postCell
		/// </summary>
		/// <param name="cell"></param>
		/// <param name="preCell"></param>
		/// <param name="cellCopy"></param>
		/// <param name="postCell"></param>
		private void Detach(SequenceCell cell, SequenceCell preCell, SequenceCell cellCopy, SequenceCell postCell)
		{
			int arci = findArc(preCell.Arcs, cell.Id);
			int arcj = findArc(cell.Arcs, postCell.Id);
			preCell.Arcs[arci].Destination = cellCopy.Id;
			cellCopy.ConnectTo(postCell.Id, cell.Arcs[arcj].Multiplicity);
			cell.Arcs.RemoveAt(arcj);
		}

		/// <summary>
		/// Relink the preCell to cellCopy, and cellCopy links to the postCell. Delink cell to postCell
		/// </summary>
		/// <param name="cell"></param>
		/// <param name="preCell"></param>
		/// <param name="cellCopy"></param>
		/// <param name="postCell"></param>
		private void Detach(SequenceCell cell, SequenceCell preCell, SequenceCell cellCopy, SequenceCell twinCell, SequenceCell twinCellCopy, SequenceCell postTwinCell)
		{
			int arci = findArc(preCell.Arcs, cell.Id);
			int arcj = findArc(cell.Arcs, twinCell.Id);
			preCell.Arcs[arci].Destination = cellCopy.Id;
			cellCopy.ConnectTo(twinCellCopy.Id, cell.Arcs[arcj].Multiplicity);
			cell.Arcs.RemoveAt(arcj);

			arci = findArc(twinCell.Arcs, postTwinCell.Id);
			twinCellCopy.ConnectTo(postTwinCell.Id, twinCell.Arcs[arci].Multiplicity);
			twinCell.Arcs.RemoveAt(arci);
		}

		private int findArc(List<Arc> arcs, long id) {
			for (int i = 0; i < arcs.Count; ++i) {
				if (arcs[i].Destination == id) {
					return i;
				}
			}
			return -1;
		}

		private void fillMatrix(ResolvableMatrix mx, SequenceCell[] preCells, SequenceCell[] postCells, int gap) {
			int i = 0;
			foreach (var preCell in preCells) {
				int[] off = new int[mx.Dimension];
				Array.Clear(off, 0, mx.Dimension);
				foreach (var read in preCell.ReadInfo)
				{
					int j = 0;
					foreach (var postCell in postCells)
					{
						int k = off[j];
						for (; k < postCell.ReadInfo.Count; ++k)
						{
							if (postCell.ReadInfo[k].ReadId > read.ReadId) {
								break;
							} else if (postCell.ReadInfo[k].ReadId == read.ReadId) {
								if (postCell.ReadInfo[k].Offset > read.Offset - gap - 1) {
									break;
								} else if (postCell.ReadInfo[k].Offset == read.Offset - gap - 1) {
									mx.Increment(i, j);
								}
							}
						}
						off[j] = k;
						++j;
					}
				}
				++i;
			}
		}

		private long GenerateFreeId()
		{
			long newId;
			do
			{
				newId = Int64ID.NewID();
			} while (bg.LoadCell<SequenceCell>(newId) != null);
			return newId;
		}

		static public void unitTest() {
			ResolvableMatrix mx = new ResolvableMatrix(3);
			Console.WriteLine(mx);
			mx.Increment(1, 2);
			mx.Increment(1, 2);
			mx.Increment(0, 0);
			mx.Increment(0, 1);
			mx.Increment(1, 0);
			Console.WriteLine(mx);
			mx.Transpose();
			Console.WriteLine(mx);
			mx.Transpose();
			Console.WriteLine(mx);
		}
	}
}
